Sabee Grewal

Sabee Grewal

I'm a Goldstine Fellow at IBM Research and a postdoc at Columbia University, where I'm hosted by Henry Yuen.

Before that, I got my PhD at UT Austin, advised by Scott Aaronson. During my PhD, I interned at IBM Research in 2024 and Google Quantum AI in 2026, and was supported by an IBM PhD Fellowship in 2024.

Research

  1. QMA has perfect completeness

    Sabee Grewal, Dorian Rudolph

    [arXiv]

  2. A quantum oracle separation between QMA(2) and QMA

    John Bostanci, Sabee Grewal, Jonas Haferkamp, Andrew Huang, Yeongwoo Hwang, Anand Natarajan, Chinmay Nirkhe

    [arXiv]

  3. No low-degree tests for quantum states

    Omar Alrabiah, Srinivasan Arunachalam, Sabee Grewal, John Wright

    [arXiv]

  4. Nearly Time-Optimal Pure State Tomography with Pauli Measurements

    Sabee Grewal, Meghal Gupta, William He, Aniruddha Sen, Mihir Singhal

    FOCS '26

    [arXiv]

  5. On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity

    Sabee Grewal, Dorian Rudolph

    ICALP '26, TQC 2026

    [arXiv] [ICALP '26]

  6. Efficient Learning of Structured Quantum Circuits via Pauli Dimensionality and Sparsity

    Sabee Grewal, Daniel Liang

    [arXiv]

  7. Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs

    Sabee Grewal, William Kretschmer

    TQC '26

    [arXiv] [ECCC]

  8. Demonstrating an Unconditional Separation Between Quantum and Classical Information Resources

    William Kretschmer, Sabee Grewal, Matthew DeCross, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nicholas Hunter-Jones, Karl Mayer, Brian Neyenhuis, David Hayes, Scott Aaronson

    Coverage: Popular Mechanics, NewScientist, Gizmodo, Phys.org, Quantum Insider, Shtetl-Optimized

    [arXiv]

  9. Computability Theory of Closed Timelike Curves

    Scott Aaronson, Mohammad Bavarian, Toby Cubitt, Sabee Grewal, Giulio Gueltrini, Ryan O'Donnell, Marien Raat

    [arXiv]

  10. Improved Circuit Lower Bounds and Quantum-Classical Separations

    Sabee Grewal, Vinayak M. Kumar

    [arXiv] [ECCC]

  11. Agnostic Tomography of Stabilizer Product States

    Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang

    Quantum (2026)

    [arXiv] [Journal]

  12. Pseudoentanglement ain't cheap: Lower bounds on the non-Clifford cost of pseudoentanglement

    Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang

    Physical Review A (2026), TQC '24

    [arXiv] [Journal]

  13. PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements

    Scott Aaronson, Sabee Grewal, Vishnu Iyer, Simon Marshall, Ronak Ramachandran

    FSTTCS '25

    [arXiv] [FSTTCS '25]

  14. The Entangled Quantum Polynomial Hierarchy Collapses

    Sabee Grewal, Justin Yirka

    CCC '24

    [arXiv] [ECCC] [CCC '24]

  15. Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates

    Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang

    Quantum (2025), QIP '24

    [arXiv] [Journal]

  16. Improved Stabilizer Estimation via Bell Difference Sampling

    Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang

    STOC '24, QIP '24

    [arXiv] [STOC '24]

  17. Efficient Tomography of Non-Interacting Fermion States

    Scott Aaronson, Sabee Grewal

    TQC '23

    [arXiv] [TQC '23]

  18. Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

    Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang

    ITCS '23

    Best Student Paper Award

    [arXiv] [ITCS '23]

  19. Classical Shadows With Noise

    Dax Enshan Koh, Sabee Grewal

    Quantum (2022)

    [arXiv] [Journal]